# 多重背包问题(Bounded Knapsack Problem)
# 在多重背包问题中, 每个物品可以被选取c[i]次或者固定次c.

"""题目
给定一个容量为W的背包和n个物品, 每个物品i有重量 wi 和价值 vi. 每个物品最多可以选择 c 次. 求解如何在不超过背包容量的情况下选取物品使得总价值最大.
"""


def bounded_knapsack_base(W: int, items: list, c: int) -> int:
    """
    W: 背包容量
    items: 每个物品的 (weight, value) 元组列表
    c: 每个物品最多可选次数
    返回能取得的最大总价值
    """
    n = len(items)
    # dp[i][j] 表示前 i 个物品在容量为 j 时获得的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    # 遍历每个物品（注意：这里 i 从 1 开始，items 中的物品下标为 i-1）
    for i in range(1, n + 1):
        wi, vi = items[i - 1]
        for j in range(W + 1):
            # 默认不选取当前物品，即继承上一行的状态
            dp[i][j] = dp[i - 1][j]
            # 枚举选取当前物品的数量 k
            for k in range(1, c + 1):
                if j >= k * wi:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * wi] + k * vi)
                else:
                    break  # 如果容量不足以放下 k 个当前物品，则无需尝试更大的 k
    return dp[n][W]


def bounded_knapsack_opt(W: int, items: list, c: int) -> int:
    """
    n: 物品数量
    W: 背包容量
    items: 每个物品的 (weight, value) 元组列表
    c: 每个物品最多可选次数
    返回能取得的最大总价值
    """
    # 初始化 dp 数组，dp[j] 表示容量为 j 时的最大价值
    dp = [0] * (W + 1)

    # 遍历每个物品
    for weight, value in items:
        # 逆序遍历背包容量，确保每个物品只使用有限次数
        for j in range(W, weight - 1, -1):
            # 枚举选择当前物品的个数 k (1 到 c)
            for k in range(1, c + 1):
                if j >= k * weight:
                    dp[j] = max(dp[j], dp[j - k * weight] + k * value)
                else:
                    break  # 如果当前容量无法放下 k 个物品，则无需继续尝试更大的 k
    return dp[W]


if __name__ == '__main__':
    W = 12
    items = [
        (2, 3),  # 物品1：重量2，价值3
        (3, 4),  # 物品2：重量3，价值4
        (2, 5)  # 物品3：重量4，价值5
    ]
    c = 6  # 每个物品最多可选的次数
    print(bounded_knapsack_base(W, items, c))  # 6->15 6->9
    print(bounded_knapsack_opt(W, items, c))
